%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsection{Übungsblatt 2, 24.10.}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (i) - \buchmann{4.16.20}}
\textbf{Aufgabe:}\\
Finden Sie eine injektiv affin lineare Abbildung $(\Z/2\Z)^3 \rightarrow (\Z/2\Z)^3$ die (1,1,1) auf (0,0,0) abbildet.

\textbf{Lösung:}
\begin{itemize}
\item Eine injektiv affine lineare Funktion hat die Form $f(v) = \mathbf{A}v+\mathbf{b}$ mit $\mathbf{A}$ invertierbar.
\vspace*{5mm}
\item[$\Rightarrow$] Injektiv affine lineare Funktion (Beispiel): $f(v) = f^{-1}(v) = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0& 1 \end{pmatrix}v+\begin{pmatrix} 1\\1\\1\end{pmatrix}$
\vspace*{5mm}
\item[$\Rightarrow$] Wertetabelle (Beispiel):
\begin{tabular}{c|c}
$v$ & $f(v)$\\
\hline
$(0,0,0)$ & $(1,1,1)$\\
$(0,0,1)$ & $(1,1,0)$\\
$(0,1,0)$ & $(1,0,1)$\\
$\vdots$ & $\vdots$\\
$(1,1,1)$ & $(0,0,0)$\\
\end{tabular}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (ii) - \buchmann{4.16.22}}
\textbf{Aufgabe:}\\
Geben Sie einen Schlüssen für eine Äffin lineare Chiffre mit Alphabet \{A,B,C, $\cdots$ ,Z\} und Blocklänge 3 an, mit dem ROT in GUT verschlüsselt wird.

\textbf{Lösung:}
\begin{itemize}
\item Tabelle Klartexte und Chiffrat
\begin{tabular}{l|c|c|c}
Alphabet A...Z & R & O & T \\
Alphabet 1...26 & 17 & 14 & 19 \\
\hline
Alphabet 1...26 & 6 & 20 & 19 \\
Alphabet A...Z & G & U & T \\
\end{tabular}\\
\vspace*{5mm}
\item lineare Funktion gewählt: $f(v) = \begin{pmatrix} x & 0 & 0\\ 0 & y & 0 \\ 0 & 0& z \end{pmatrix}v+\begin{pmatrix} 0\\0\\0\end{pmatrix}$\\
\vspace*{5mm}
\item es ergibt sich somit ein lineares Gleichungssystem: 
\begin{align*}
17x &\equiv 6 \mod 26\\
14y &\equiv 20 \mod 26\\
19z &\equiv 19 \mod 26
\end{align*}
\begin{align*}
17x &\equiv 6 \mod 26\\
17*23x &\equiv 20*23 \mod 26 \\
x &\equiv 8 \mod 26
\end{align*}
\begin{align*}
14y &\equiv 20 \mod 26\\
7y &\equiv 10 \mod 13\\
7*2y &\equiv 10*2 \mod 13\\
y &\equiv 7 \mod 13\\
(y &\equiv 20 \mod 13)
\end{align*}\\
\vspace*{0mm}
\item[$\Rightarrow$] Ergebnis
\begin{displaymath}
f(v) = \begin{pmatrix} 8 & 0 & 0\\ 0 & 7 & 0 \\ 0 & 0& 1 \end{pmatrix}v+\begin{pmatrix} 0 \\ 0 \\ 0\end{pmatrix}
\end{displaymath}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (iii) - \buchmann{6.5.3}}
\textbf{Aufgabe:}\\
Zeigen Sie, dass für $m,k \in \{0,1\}^{64}$ immer $\overline{DES(m,k)}=DES(\overline{m},\overline{k})$ gilt.

\textbf{Lösung:}
\begin{itemize}
\item Allgemein: $\overline{b}$ bedeutet bitweise Investierung von $b$
\item DES ist eine Erweiterung der Feistel-Chiffre \\
$\Rightarrow$ Verschlüsselungsfunktion pro Runde effektiv: $E(R)\oplus K$.  
\item Expansionsfunktion $E(R): \{0,1\}^{32}\rightarrow \{0,1\}^{48}$ 
\item 16 Abbildungen doppelt \\ 
$\Rightarrow \overline{E(R)}=E(\overline{R})$.
\item Selbiges gilt für den Rundenschlüssel $K_i$. \\
$\Rightarrow \overline{K_i(k)}=K_i(\overline{k})$.
\item per Definition ist XOR:  
\begin{tabular}{c|c|c}
$\oplus$ & 0 & 1 \\
\hline
0 & 0 & 1  \\
\hline                                   
1 & 1& 0 \\
\end{tabular}
\item[$\Rightarrow$] $\overline{DES(m,k)}=DES(\overline{m},\overline{k})$
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (iv) - \buchmann{6.5.5}}
\textbf{Aufgabe:}
\begin{enumerate}
\item Zeigen Sie, dass $C_{16}$ und  $D_{16}$ aus $C_{1}$ und  $D_{1}$ durch einen zirkulären Linksshift der Länge 1 entsteht.
\item Gelte $K_{1}=K_{2}=\cdots=K_{16}$. Zeigen Sie, dass alle Bits in $C_{1}$ gleich sind und ebenso alle Bits in $D_{1}$ gleich sind.
\item Folgern Sie, dass es genau vier DES-Schlüssel gibt, die für alle Teilschlüssel gleich sind. Dies sind die schwachen DES-Schlüssel.
\item Geben Sie die vier schwachen DES-Schlüssel an. Es genügt PC1($k$) statt $k$ anzugeben.
\end{enumerate}


\textbf{Lösung - Teil 1:}
\begin{itemize}
\item $C_{16} = C_0$ (per Definition). 
\item Linksshift$_1(C_0)=C_1$
\item[$\Rightarrow$] Rechtsshift$_1(C_1)=C_0$
\item[$\Rightarrow$] Analog auch für $D_{16}$: Rechtsshift$_1(D_1)=D_0$
\end{itemize}
Hinweis: Nicht zu verwechseln mit dem $C_{j}$ aus den S-Boxen mit 1$ \le  j \le  8$ und 
$C_{i} = C_{i,1}C_{i,2}C_{i,3}C_{i,4}C_{i,5}C_{i,6}C_{i,7}C_{i,8}$ .

\textbf{Lösung - Teil 2 (sehr gute Lösung im Buch!):}
\begin{itemize}
\item Sei $K_i$ der $i$-te Rundenschlüssel (mit den Bits 0 bis 47) und $C_i$ bzw. $D_i$ der Länge 28 für $1 \le i \le 16$.  
\item In PC2 erfolgt keine Permutation auf das 9,18,22 und 25 Bit.
\item Es gilt $K_i=\operatorname{PC2}(C_i,D_i)$
\item mit $K_1 = K_{16}$ und $C_{1,j} = C_{16,j+1}$ mit $0 \le j \le 26$ folgt:\\
$C_{1,i}=C_{1,i+1}$ für alle $i+1 \in \{9,18,22,25\}$ und \\
$C_{16,i}=C_{1,i+1}$ für alle $i \in \{9,18,22,25\}$\\
$\Rightarrow$ $C_{1,0} \cdots C_{1,8}, C_{1,9} \cdots C_{1,17}, C_{1,18} \cdots C_{1,21} ,C_{1.22} \cdots C_{1,24}$
und 
$C_{1,25} \cdots C_{1,27}$
sind jeweils gleich.
\item Mit $K_1 =K_2$ und $C_{1,j} = C_{16,j+}$ folgt dann analog: 
$C_{1,8} =C_{1,9}, C_{1,17}=C_{1,18}, C_{1,21} =C_{1,22}$
und $C_{1,24} =C_{1,25}$
\item[$\Rightarrow$]  Da $K_1=K_2=\cdots=K_{16}$
ist unsere Behauptung bewiesen.
\end{itemize}

\textbf{Lösung - Teil 3:}
\begin{itemize}
\item  alle Bits $C_{1,1} \cdots C_{1,28}$ = 0
\item  alle Bits $D_{1,1} \cdots D_{1,28}$ = 0 
\item  alle Bits $C_{1,1} \cdots C_{1,28}$ = 1
\item  alle Bits $D_{1,1} \cdots D_{1,28}$ = 1 
\item In allen anderen Zuständen sind die Teilschlüssel nicht gleich.
\item [$\Rightarrow$] Es gibt genau 4 schwache Schlüssel
\end{itemize}

\textbf{Lösung - Teil 4:}
\begin{itemize}
\item $k$ = 0x 01 01 01 01 01 01 01 01\\ $\Rightarrow$ PC1($k$) = 00000000000000
\vspace*{5mm}
\item $k$ = 0x FE FE FE FE FE FE FE FE) \\ $\Rightarrow$ PC1($k$)  = FFFFFFFFFFFFFF
\vspace*{5mm}
\item $k$ = 0x 1F 1F 1F 1F 0E 0E 0E 0E) \\ $\Rightarrow$ PC1($k$)  = 0000000FFFFFFF
\vspace*{5mm}
\item $k$ = 0x E0 E0 E0 E0 F1 F1 F1 F1)\\ $\Rightarrow$ PC1($k$)  =FFFFFFFF0000000
\end{itemize}
 
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (v) - \buchmann{3.23.26}}
\textbf{Aufgabe:}
\begin{enumerate}
\item Begründen Sie, dass ein Polynom vom Grad $k$ genau dann irreduzibel ist, wenn es von keinem irreduziblen Polynom von kleinerem Grad geteilt wird. 
\item Geben Sie dann alle irreduziblen Polynome bis zum Grad 4 an.
\item Zeigen Sie, dass das Polynom $f(x)=x^8+x^4+x^3+x+1$ in $(\Z/2\Z)[X]$ irreduzibel ist.
\end{enumerate}


\textbf{Lösung - Teil 1:}
\begin{itemize} 
\item Jedes reduzible Polynom lässt sich darstellen als Produkt von Polynomen (:="Teil-Polynom") (kleineren Grades)
\item Entweder das Teil-Polynom ist reduzibel und lässt sich wieder als Produkt darstellen... \textit{(rekursiv)}
\item Oder das Teil-Polynom ist irreduzibel.
\item[$\Rightarrow$] Jedes reduzible Polynom lässt sich darstellen als Produkt von irreduziblen Polynomen
\vspace*{5mm}
\item[$\Rightarrow$] Es folgt auch der Umkehrschluss: Lässt sich ein Polynom nicht durch ein irreduziblen Polynomen (kleineren Grades) teilen, so ist es selbst irreduzibel.
\end{itemize}

\textbf{Lösung - Teil 2:}
\begin{itemize} 
\item Vorgehen: 
\begin{itemize} 
\item Polynom $f$ vom Grad $n$
\item Division von $f$ durch alle irreduziblen Polynome $g$ von Grad $\le n/2$ ausprobieren
\item Wenn $g \nmid f$ für alle $g$ gilt, so ist $f$ irreduzibel
\end{itemize} 
\vspace*{5mm}
\item[$\Rightarrow$] Alle irreduziblen Polynome bis 4.Grad sind:
\begin{alignat*}{2}
\{&1,&&\text{Grad }0\\
&x, x+1,&&\text{Grad }1\\
&x^2+x+1,&&\text{Grad }2\\
&x^3+x+1, x^3+x^2+1,&&\text{Grad }3\\
&x^4+x+1, x^4+x^3+1, x^4+x^3+x^2+x+1\}&\qquad&\text{Grad }4
\end{alignat*}
\begin{itemize}
\vspace*{-6mm}
\item Hinweis: Das Nullpolynom ist nicht irreduzibel!
\end{itemize}
\end{itemize}

\textbf{Lösung - Teil 3:}
\begin{itemize} 
\item $f(x)=x^8+x^4+x^3+x+1 \text{ in }(\Z/2\Z)$
\vspace*{3mm}
\item Testen der irreduziblem Polynome von Grad 1 als Divisior:\\
entspricht Prüfen auf Nullstellen, $f(0) = f(1) \equiv 1 \mod 2$\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 1 teilbar.
\vspace*{3mm}
\item Testen des irreduziblen Polynoms von Grad 2 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^2+x+1}}\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 2 teilbar!
\item Testen der irreduziblem Polynome von Grad 3 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^3+x+1}}\\
... weitere ...\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 3 teilbar!
\item Testen der irreduziblem Polynome von Grad 4 als Divisior:\\
{\tiny \polylongdiv{x^8+x^4+x^3+x+1}{x^4+x^3+1}}\\
... weitere ...\\
$\Rightarrow$ Polynom $f$ nicht durch Polynom mit Grad 3 teilbar!
\vspace*{5mm}
\item[$\Rightarrow$] Polynom irreduzibel!
\end{itemize}


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (vi) - One Time Pad}
\textbf{Aufgabe:}\\
Fällt beim One-Time-Pad (OTP) die Wahl des Schlüssels ausgerechnet auf $\hat{k} = 0 \ldots 0$, so wird der Klartext effektiv unverschlüsselt gesendet. Daher wird vorgeschlagen, den Schlüssel zufällig und gleichverteilt aus der Menge $\{ 0, 1 \}^n \setminus \{\hat{k}\}$ auszuwählen. Ist das eine Verbesserung? Beweisen Sie Ihre Antwort. Falls ja, zeigen Sie, dass das modifizierte OTP immer noch perfekt geheim ist und begründen Sie, wieso das OTP nicht gleich so beschrieben wurde. Falls nein, bringen Sie das in Einklang mit der Tatsache, dass bei $\hat{k}$ gar nicht verschlüsselt wird.

\textbf{Lösung:}\\
Die sog. Verbesserung taugt nichts, da dadurch die perfekte Sicherheit verloren geht:\\[4mm]
Schlüsselraum: $K' = K\backslash\{\hat{k}\}$ wobei $K=\{0,1\}^n$\\
Verschlüsselung: $OTP'_k : P=\{0,1\}^n \longrightarrow C=\{0,1\}^n$ mit $p \longmapsto p \xor k$\\
Definition perfekt geheim: $\forall p \in P, \forall c \in C$ gilt  $\text{Pr}(p|c)=\text{Pr}(p)$\\
Shannon: 
Äquivalent dazu, dass $\forall k \in K' \text{Pr}(k)=\frac{1}{|K'|} $ (1) 
und $\forall p \in P, \forall c \in C \exists k \in K'$ sodass $c=OTP'_k(p)$ (2).\\
$\Rightarrow$ Bedingung (2) kann nicht erfüllt werden für $c=p$, da $\hat{k}=000\cdots0 \notin K'$.\\[2mm]
Der Fall, dass (mit Wahrscheinlichkeit  $\frac{1}{|K|}=2^{-n}$) $\hat{k}=000\cdots0$ für das OTP ausgewählt wird, muss nicht ausgeschlossen werden, denn der Angreifer weiß ja nicht, dass dieses $\hat{k}$ gewählt wurde. Das Chiffrat $c=000\cdots0 \xor p$ könnte ja genauso aus $p' \in P$ und $k=p \xor p'$ entstanden sein.


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (vii) - Feistel Chiffre}
\textbf{Aufgabe:}\\
Wie lautet die Ausgabe eines Feistel-Netzwerks mit $r$ Runden, falls für die Rundenfunktion $f$ gilt $f(x) = 0 \ldots 0$ f¸r alle $x$. Was ist im Fall $f(x) = x$?

\textbf{Lösung:}\\
Feistel Chiffre mit 
\newline
$f(x)=0:\qquad(L_{i},\enspace R_{i}) = (R_{i-1},\enspace L_{i-1} \xor 0) =  (R_{i-1},\enspace L_{i-1} )$
\newline
Damit ergibt sich für
\begin{itemize}
\item $r \mod 2 = 1:\qquad (L_{r},\enspace R_{r}) = (R_{0},\enspace L_{0})$
\item $r \mod 2 = 0:\qquad (L_{r},\enspace R_{r}) = (L_{0},\enspace R_{0})$
\end{itemize}
\vspace{5mm}
Feistel Chiffre mit
\newline
$f(x)=x:\qquad(L_{i},\enspace R_{i}) = (R_{i-1},\enspace L_{i-1} \xor R_{i-1})$
\newline
Damit ergibt sich für
\begin{itemize}
\item $r \mod 3 = 1:\qquad (L_{r},\enspace R_{r}) = (R_{0},\enspace L_{0} \xor R_{0})$
\item $r \mod 3 = 2:\qquad (L_{r},\enspace R_{r}) = (L_{0} \xor R_{0},\enspace L_{0})$
\item $r \mod 3 = 0:\qquad (L_{r},\enspace R_{r}) = (L_{0},\enspace R_{0})$
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (viii) - Strukturgleichheit?}
\textbf{Aufgabe:}\\
Zeigen Sie, dass $\gf(2^2)$ nicht  strukturgleich (isomorph) zu $\Z/4\Z$ ist, obwohl beide Mengen $4$ Elemente besitzen. Verallgemeinern Sie die Aussage für $\gf(p^k)$ und $\Z/p^k\Z$.

\textbf{Lösung:}
\begin{itemize}
\item $\gf(2^{2})$ mit dem Vertretersystem $\{0, 1, X, X+1\}$
\begin{itemize}
\item ist ein endlicher Körper
\item alle Elemente außer $0$ invertierbar bzgl. Multiplikation
\end{itemize}
\vspace*{5mm}
\item $\Z/4\Z=\{4\Z, 1 + 4\Z, 2+4\Z, 3+4\Z\}$\\
\begin{itemize}
\item ist kein Körper
\item $0$ und $2$ nicht invertierbar bzgl. Multiplikation 
\item $2+4\Z$ nicht invertierbar bzgl. Multiplikation wegen $\gcd(2,4)=2\neq1$\\  
\end{itemize}
\vspace*{5mm}
\item[$\Rightarrow$]$\gf(2^{2})$ nicht isomorph zu $\Z/4\Z$\\
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection*{Übung (ix) - Kongruenz von Polynomen}
\textbf{Aufgabe:}\\
Berechnen Sie eine Lösung $f$ von $(x^7 + x^6 + x^3 + x^2) \cdot f(x) \equiv x^4 + x + 1 \mod m(x)$ wobei $m(x) = x^8 + x^4 + x^3 + x + 1$. \emph{Hinweis:} verwenden Sie, dass bei AES $\gf(2^8)$ mittels $m(x)$ konstruiert wurde und die Tabelle am Ende der Webseite \url{http://www.samiam.org/galois.html}.

\textbf{Lösung:}
\begin{itemize}
\item Umwandeln in Bit-Schreibweise
\begin{alignat*}{10}
g(x)&=&&1x^7&+&1x^6&+&0x^5&+&0x^4&+&1x^3&+&1x^2&+&0x^1&+&0x^0\\
b_{bin}&=&&1&&1&&0&&0&&1&&1&&0&&0&\\
b_{hex}&=&&C&&&&&&&&C&&&&&&&\\
\end{alignat*}
\item  Inverses aus Tabelle ablesen (da AES)
\begin{alignat*}{10}
b^{-1}_{hex}&=&&1&&&&&&&&B&&&&&&&\\
b^{-1}_{bin}&=&&0&&0&&0&&1&&1&&0&&1&&1&\\
g^{-1}(x)&=&&0x^7&+&0x^6&+&0x^5&+&1x^4&+&1x^3&+&0x^2&+&1x^1&+&1x^0\\
\end{alignat*}
\item Umformen der Gleichung
\begin{alignat*}{2}
g(x)*f(x)&\equiv (x^4+x+1) &&\mod m(x)\\
g(x)*g^{-1}(x)*f(x)&\equiv g^{-1}(x)*(x^4+x+1) &&\mod m(x)\\
f(x)&\equiv (x^8+x^7+x^4+x^3+x^2+1) &&\mod m(x)\\
\end{alignat*}
\item Polynomdivision
{\scriptsize
\polylongdiv{x^8+x^7+x^4+x^3+x^2+1}{x^8+x^4+x^3+x+1}\\
}
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis\\
\begin{displaymath}
f(x)=x^7+x^2+x 
\end{displaymath}
\end{itemize}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\subsubsection{Übung (x) - Inverses Polynom?}
\textbf{Aufgabe:}\\
Sei $\gf(2^4)$ definiert mit Hilfe von $m(x) = x^4 + x + 1$. Berechnen Sie die Inversen in $\gf(2^4)$ von $f(x)=x$ und $g(x)=x^3+x$ mittels euklidischem Algorithmus.

\textbf{Lösung - $f(x)$ - Schlechtes Beispiel für erw. Euklid:}
\begin{itemize}
\item für $f(x)=x$, $m(x)=x^4+x+1$
\item Polynomdivision\\
\polylongdiv{x^4+x+1}{x}
\item $q(x)=x^3+1$, $r = 1$
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis: $f^{-1}(x)=x^3+1$
\end{itemize}

\textbf{Lösung - $g(x)$ - Besseres Beispiel für erw. Euklid:}
\begin{itemize}
\item für $g(x)=x^3+x$, $m(x)=x^4+x+1$
\vspace*{5mm}
\item Polynomdivision 1\\
\polylongdiv{x^4+x+1}{x^3+x}\\
$\Rightarrow q_1(x)=x,\qquad r_1(x) = x^2+x+1$
\item Da der Rest der vorigen Polydiv ungleich 1\\
$\Rightarrow$ Polydiv mit Divisor durch Rest
\vspace*{2mm}
\item Polynomdivision 2\\
\polylongdiv{x^3+x}{x^2+x+1}\\
$\Rightarrow q_2(x)=x+1,\qquad r_2(x) = x+1$
\item Da der Rest der vorigen Polydiv ungleich 1\\
$\Rightarrow$ Polydiv mit Divisor durch Rest
\vspace*{2mm}
\item Polynomdivision 2\\
\polylongdiv{x^2+x+1}{x+1}\\
$\Rightarrow q_3(x)=x,\qquad r_3(x) = 1$
\item Rest der vorigen Polydiv gleich 1\\
$\Rightarrow$ fertig!
\vspace*{2mm}
\item Tabelle für erweiterten Euklid\\
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\rowcolor{grau} $k$ & 0 & 1 & 2 & 3 & 4 \\
\hline
$r_k$ & $x^4+x+1$ & $x^3+x$ & $r_2(x)=x^2+x+1$ & $r_2(x)=x+1$ & $r_3(x)=1$\\
\hline
$q_k$ & --- & $q_1(x)=x$ & $q_2(x)=x+1$ & $q_3(x)=x$ & $x+1$ \\
\hline
$x_k$ & 1 & 0 & 1 & $x$ & $x^2+1$\\
\hline
$y_k$ & 0 & 1 & $x$ & $x^2+x+1$ & \cellcolor{rot}$x^3+x^2$\\
\hline
\end{tabular}
\normalsize
\vspace*{5mm}
\item[$\Rightarrow$] Ergebnis: $g^{-1}(x)=x^3+x^2$
\end{itemize}
